def make_mat(m, n, fill=None):
    mat = []
    for i in range(m):
        mat.append([fill] * n)
    return mat

VACAN = -1e6


class Solution:
    def __init__(self):
        self.board = []
        self.rank = 0

    def check(self, i, j):
        for k in range(1, self.rank):
            if (self.board[k] == j) or (j-i == self.board[k] - k) or (i+j == self.board[k] + k):
                return False
        return True

    def show(self):
        for i in reversed(self.board[1:]):
            buf = "." * (i-1) + "*" + "." * (self.rank - i)
            print(buf)
        print("\n=========\n")

    def queen(self):
        num = 0
        i = 1
        j = 1
        self.board = [VACAN] * (self.rank + 1)

        while i <= self.rank:
            while j <= self.rank:
                if self.check(i, j):
                    self.board[i] = j
                    j = 1
                    break
                else:
                    j += 1
            if self.board[i] == VACAN:
                if i == 1:
                    break
                else:
                    i -= 1
                    j = self.board[i] + 1
                    self.board[i] = VACAN
                    continue
            if i == self.rank:
                num += 1
                # print(self.board[1:])
                self.show()
                j = self.board[i] + 1
                self.board[i] = VACAN
                continue
            i += 1
        return num


if __name__ == '__main__':
    s = Solution()
    s.rank = 8
    s.queen()
